perm filename GEM[0,BGB]14 blob
sn#109017 filedate 1974-07-03 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 ~[CαGEOMETRIC MODELING THEORY.
C00004 00003 [1.1 Kinds of Geometric Models.]
C00006 00004 For a naive start, first consider a 3-D array in which each
C00010 00005
C00013 00006
C00016 00007
C00019 00008
C00022 00009
C00024 00010 ~FC1.2 Polyhedron Definitions.
C00028 00011 ~FC1.3 Camera, Light and Image Modeling.
C00035 ENDMK
C⊗;
~[C;αGEOMETRIC MODELING THEORY.;
λ30;I425,0;P5;JCFA SECTION 1.
~JCFD GEOMETRIC MODELING THEORY.
~I950,0;JUFA
[1.0 Introduction to Geometric Modeling.]
In the specific context of computer vision and graphics,
geometric modeling refers to constructing computer representations of
physical objects, cameras, images and light for the sake of
simulating their behavior. In Artificial Intelligence, a geometric
model is a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that it is quantitative and numerical rather than qualitative and
symbolic. The notion of a world model requires an external world
environment to be modeled, an internal computer environment to hold
the model, and a task performing entity to use the model. In
geometry, modeling is a synthetic problem, like a construction with
ruler and straight edge, modeling problems require an algorithmic
solution rather than a proof. The adjective "geometric" however is
quite apropos in that it literally means "world measure" which is
exactly the activity to be automated.
~Q;F.
[1.1 Kinds of Geometric Models.]
The main problem of geometric modeling is to invent good
methods for representing arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid, opaque,
Newtonian and macroscopic with a mathematically well behaved surface.
Physical objects include: the earth, chairs, roads, and plastic toy
horses. Physical objects may be moved about in space,
but two objects can not simultaneously occupy the same space at the
same time. The scope of the problem can be appreciated by examining
the virtues and drawbacks of the kinds of models listed in box 1.1 below.
~|------------------------------------------λ10;JAFA
BOX 1.1~JCFA TEN KINDS OF GEOMETRIC MODELS.
~↓F.
Space Oriented:
1. 3-D Space Array.
2. Recursive Cells.
3. 3-D Density Function.
4. 2-D Surface Functions.
5. Parametric Surface Functions.
~↑W640;F.
Object Oriented:
6. Manifolds.
7. Polyhedra.
8. Volume Elements.
9. Cross Sections.
10. Skeletons.
~|---------------------------------------λ30;JUFA
For a naive start, first consider a 3-D array in which each
element indicates the presence or absence of solid matter in a cube
of space. Such a 3-D space array has the very desirible properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and natural form. Spatial addressing refers to finding out what the
model contains within a distance R of a locus X,Y,Z; spatial
uniqueness refers to modeling the property that physical solids can
not occupy the same space. The main drawback of the 3-D space array
model is illustrated by the apparently legal FORTRAN statement:
~JC;F.DIMENSION SPACE(10000,10000,10000)
The problem with such a dimension statement is that no
present day computer memory is large enough to contain a 10↑15
element array. Smaller space arrays arrays can be useful but
necessarily can not model large volumes with high resolution. A
further drawback of space arrays is that objects and surfaces are not
readily accessible as entities; that is a space array lacks the
desirible property of "object coherence".
The space array idea can be salvaged because large portions
of the array contain similar values. By grouping blocks of elements
with the same values together, the addressing process becomes more
complicated but the overall memory required is reduced and the two
desired properties can be maintained. One way of doing this (which
has been discovered in several applications) is "recursive cells";
the whole space is considered to be a cell; if the space is not
homogeneous than the first cell is divided into two (or four or
eight) sub cells and the criterion is applied again. This technique
of recursive celling allows the spatial sorting of objects, if the
object models can be subdivided at each recursion without losing the
properties of the objects.
In mathematical physics, arbitrary physical objects are
frequently referred to as three dimensional density functions
W=RHO(X,Y,Z). Unfortunately such density functions can not be written
out for objects such as a typing chair or a plastic horse without
resorting to a programming language or an extensive table (which is
equivalent to the space array model). Some special objects however
are essentially 2-D and can be approximated by surface funtion Z =
F(X,Y). For example geodetic maps are handled by computer in
such a fashion.
By definition, a function is single valued; consequently the
description of even modestly complicated objects can not be expressed
directly as a single function of orthogonal rectilinear space
coordinates X, Y and Z. It is necessary either to adopt parametric
functions or to subdivide the object into portions that can be
described by simple functions of Cartesian variables. The latter
course of subdividing objects into portions is called segmentation
and is discussed later; the former course can be illustrated by the
example in figure ** showing (X,Y,Z) locus of the surface of a unit
cube expressed as functions of (U,V) surface coordinates. The
advantage of parametric functions is that extended arbitrary curve
surfaces can be expressed; some of the disadvantages are that
parametric curves may be self intersecting, they are not easy to
modified locally, and the functions become impractically complex
before interesting objects are achieved.
In passing from space oriented models to object oriented
models, I wish to point out the mysterious dichotomy between objects
and the space that contains the objects, and observe that the same
dichotomy appears in the foundations of physics. However, our goal
is merely to simulate the properties of objects; rather than to
explain them. In this regard, the representation of time will
receive no special attention; although an advanced problem solving
robot will want to run world simulations along multiple time paths,
the present discussion will be restricted to simulations along one
time path.
After existence in space and time, another general property
of physical objects is that they can be enclosed by an unbroken two
dimensional surface with an unabiguous inside and outside. Which
touchs upon the mathematical topic (celebrated in song by Tom Lehrer)
of the algebraic topology of locally Euclidean transitions of
infinitely differentiable oriented Riemann manifolds. A manifold is
the mathematical abstraction of a surface; a Riemann manifold has a
metric function; an oriented manifold has a unambiguous inside and an
outside; the phrase "infinitely differentiable" can be taken to mean
that the surface is smooth and continuous; and the phrase "locally
Euclidean transitions" refers to the process of segmenting the object
into portions that can be approximated by relatively simple
functions. In particular, the 2-D Riemann (sub)manifold embedded in
3-D Euclidean space is the mathematical object that comes closest to
representing the shape and extent of the surface of a physical
object; such manifolds lead directly to the topology of surfaces
which in turn is a convenient computational approach to polyhedra.
The topology of a 2-D Riemann submanifold embedded in a 3-D
Euclidean space is composed of three kinds of simplex: the 0-Simplex
(or vertex), the 1-Simplex (or edge), and the 2-Simplex (or
triangle). In topological analysis, it may be demonstrated that such
2-D Riemann submanifolds may be divided into simplex such that Eulers
equations F-E+V=2-2*H is satisfied (where F is the number of
2-simplex, E is the number of 1-simplex, V is the number of
0-simplex and H is the genus (number of handles) of the manifold);
and such that the surface of the manifold can be approximated by
local functions over each 2-simplex which are Euclidean and which
splice together correctly at all the 1-simplex (edges). By
introducing a sufficient (but finite) number of triangles the
manifold can be approximated to within an epsilon, by constant
functions; yielding the geometric object called the "polyhedron".
The main inherent advantage of a polyhedral model is its
coherent surface topology of faces, edges and vertices. Such a
surface can be subdivided without losing its coherence or the
coherence of the object. The disadvantages of polyhedra include the
lack of spatial uniqueness and spatial addressing; necessitating
computation to be done to detect and prevent spatial conflict and to
find the portions of an entity occupying a given volume. Another
disadvantage is that polyhedra per se are not curved surfaces,
however by associating an appropriate function with each face a model
of a 2-D Riemann manifold can be made, which is a curved object
representation.
Returning to the survey, arbitrary objects can also be
described by listing a set of cross sections taken at a sufficient
number of cutting planes; this is how the shape of a ship's hull or
an airplane's wing is specified. Cross sections have the interesting
feature of good space modeling on one axis. Forsaking arbitrary
shaped objects, large classes of things can be described in terms of
a small set of basic volume elements. For example, Roberts and
others have built models of familar objects using only rectangular
and triangular right prisms. Although, arbitrary solid polyhedra can
be constructed out of tetrahedrons (the 3-simplex); no significant
modeling system exists using this potentially interesting approach.
Skeletal models are based on abstracting an object into a
stick figure and by associating a diameter or set of cross sections
with the sticks. In particular, spine cross section models have been
pursued at Stanford by (Agin, Binford and Nervatia; Blum). Spine
cross section models have the advantage of being able to express many
objects in a concise form suitable for recognition, however spine
cross section models can not be used directly for arbitrary shapes.
Finally, it is useful to represent physical objects by a very weak
model such as by using sets of spheres or sets of surface points. It
is interesting to note that the "reality" that the robot in
Winograd's thesis could talk about, was a blocks world based on a
geometric model consisting only of points, size of block, and a two
page LISP subroutine named FINDSPACE.
To the best of my knowledge, this survey is complete; as of
this year, 1974, there are no other significantly different kinds of
simple geometric models. The desirable properties that have turned up
in this survey are included in the list below. The final desirable
property is that there be some hope that the computer can derive the
model by measurements it can make itself, although it is quite likely
that one model will be best for input and another model will be best
for simulation.
~|---------------------------------------------------------------λ10;JAFA
BOX 1.2 DESIRABLE PROPERTIES FOR A GEOMETRIC MODEL.
1. Spatial Addressing.
2. Spatial Uniqueness.
3. Object Coherence with Divisibility.
4. Surface Coherence with Divisibility.
5. Shape generality.
6. Large Extent with High Resolution.
7. Readily Modifiable.
8. Suitable for photometric, kinematic and dynamic simulation.
9. Feasible memory and computation requirements.
10. Potential for automatic model acquistion.
~|--------------------------------------------------------------λ30;JUFA
Meta modeling ideas
prototype/instance and parts structure.
~FC1.2 Polyhedron Definitions.
~JUFA
There are essentially three kinds of {polyhedron} definition:
topological, geometrical and algebraic.
Each definition emphases a different aspect of the concept so
that in simple forms the definitions fall short of being
equivalent.
Topologically, the surface elements of a polyhedron forms a
graph that satisfies Euler's F-E+V=2-2*H equation; where F, E and V
are the number of faces, edges and vertices of the polyhedron; and
where H is the number of holes in (or genus of) the polyhedron.
However, not all Eulerian graphs of faces, edges and vertices
correspond to solid polyhedra.
Geometrically, a polyhedron is a simply connected finite
region of space composed of the union of a finite number of convex
polyhedra. A convex polyhedron is a non empty, simply connected,
finite region of space enclosed by a finite number of planes. The
boundary of the polyhedron is called its surface. The simply
connected regions of the surface belonging to only one plane are
called faces. The simply connected regions of the surface belonging
to exactly two planes are called edges; and the loci of the surface
where three or more planes interect are called vertices.
~|---------------------------------------------------------------λ10;JAFA
BOX 1.3 Properties of a Solid Polyhedron:
1. [EULERIAN]. Satisfies Eulers Equation F-E+V=2*B-2*H
2. [TRIVALENCE]. All vertices and faces have three or more edges.
3. [NON-SELF-INTERSECTION]. No edge intersects a face or vertex
to which it is not topologically linked.
4. [FACE PLANARITY]. All the vertices of a face are coplanar.
5. [SIMPLY CONNECTED SOLIDITY]. The volume measure is finite and positive.
6. [FACE CONVEXITY]. All the faces are convex.
7. [FACE SIMPLY CONNECTED PERIMETER].
~|---------------------------------------------------------------λ30;JUFA
~FC1.3 Camera, Light and Image Modeling.
~JUFA
Common to both computer graphics and vision is the necessity
to model cameras, light and images so that pictures may be
synthesized or analysized. The reader completely naive to camera
modeling is emphatically warned that all camera discussion in this
paper refers to a logical camera geometry rather than to a physical
camera geometry, the difference is illustrated in figure **.
The basic camera model that I use has eight degrees of freedom: three
in location, three in orientation and two in projection.
LOCATION: CX, CY, CZ vector to camera lens center.
ORIENTATION: WX, WY, WZ Orientation vector.
PROJECTION: AR, FR Aspect Ratio and Focal Ration.
The light scattering properties of ordinary surfaces can be
modeled by thinking of the surface as composed of many
little mirrors. The orientation of each mirror is described by two
angles, its tilt from the normal vector of the surface and its pan
about the normal vector with respect to a specified reference vector
in the tangent plane of the surface. For a perfect reflecting surface
all the differential mirrors have a zero pan and tilt; for isotropic
conventional surfaces the statistical distribution of pan
orientations is flat and the distribution of tilt orientations is a
blip function; and for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.